import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Codec {

    // 序列化二叉树为字符串
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }

        StringBuilder result = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        result.append("[");

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                result.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.append("#,");
            }
        }

        // 删除最后一个逗号
        result.deleteCharAt(result.length() - 1);
        result.append("]");

        return result.toString();
    }

    // 反序列化字符串为二叉树
    public TreeNode deserialize(String data) {
        if (data.equals("[]")) {
            return null;
        }

        String[] nodes = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!nodes[index].equals("#")) {
                node.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(node.left);
            }
            index++;

            if (!nodes[index].equals("#")) {
                node.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(node.right);
            }
            index++;
        }

        return root;
    }

    public static void main(String[] args) {
        Codec codec = new Codec();

        // 构造示例二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        // 序列化
        String serializedData = codec.serialize(root);
        System.out.println("Serialized Tree: " + serializedData);

        // 反序列化
        TreeNode deserializedRoot = codec.deserialize(serializedData);
        System.out.println("Deserialized Tree: " + codec.serialize(deserializedRoot));
    }
}
